package com.yusong.algorithm.retrospect;


import com.sun.deploy.util.ArrayUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 回溯思想解决0-1背包问题
 * 动态规划
 */
public class Bag01 {

    //物品数据
    private static final int[] DATA = {10, 7, 9, 5 ,3, 1};

    private static final String[] PARA = {"0", "0", "0", "0" , "0", "0"};
    //最大重量
    private static final int LIMIT = 19;
    //当前最大重量 不能使用全局变量
    private static int maxCurrentWeight = Integer.MIN_VALUE;

    /**
     * 记忆化搜索+递归；用二维数组作为结果存储。
     * 根据缓存结构推导动态规划，可以认为使用动态规划降维
     * @param index
     * @param currentWeight
     */
    private static void put(int index, int currentWeight){
        //终止条件
        if(index == DATA.length || currentWeight == LIMIT){
            if(maxCurrentWeight <= currentWeight){
                maxCurrentWeight = currentWeight;
                System.out.println(ArrayUtil.arrayToString(PARA) +" = "+maxCurrentWeight);
                return;
            }
            return;
        }
        //不放入
        PARA[index] = "0";
        put(index +1, currentWeight);
        int indexWeight = DATA[index];
        if(currentWeight + indexWeight <= LIMIT){
            PARA[index] = "1";
            put(index +1, currentWeight+indexWeight);
        }
    }


    /**
     * 动态规划:我们把问题分解为多个阶段，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合（去掉重复的）
     * ，然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。
     * 缺点：需要额外申请一个 n 乘以 w+1 的二维数组，对空间的消耗比较多。
     */
    //weight:物品重量，n:物品个数，w:背包可承载重量
    public int knapsack(int[] weight, int n, int w) {
        boolean[][] states = new boolean[n][w+1]; // 默认值false
        states[0][0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
        if (weight[0] <= w) {
            states[0][weight[0]] = true;
        }
        for (int i = 1; i < n; ++i) { // 动态规划状态转移
            for (int j = 0; j <= w; ++j) {// 不把第i个物品放入背包
                if (states[i-1][j] == true) states[i][j] = states[i-1][j];
            }
            for (int j = 0; j <= w-weight[i]; ++j) {//把第i个物品放入背包
                if (states[i-1][j]==true) states[i][j+weight[i]] = true;
            }
        }
        for (int i = w; i >= 0; --i) { // 输出结果
            if (states[n-1][i] == true) return i;
        }
        return 0;
    }

    /**
     *优化： 时间换空间
     * 另一种方法:奇 偶分行。节省空间
     */
    public static int knapsack2(int[] items, int n, int w) {
        boolean[] states = new boolean[w+1]; // 默认值false
        states[0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
        if (items[0] <= w) {
            states[items[0]] = true;
        }
        for (int i = 1; i < n; ++i) { // 动态规划
            for (int j = w-items[i]; j >= 0; --j) {//把第i个物品放入背包
                if (states[j]==true) states[j+items[i]] = true;
            }
        }
        for (int i = w; i >= 0; --i) { // 输出结果
            if (states[i] == true) return i;
        }
        return 0;
    }


    //加入物品价值复杂度
    //们把每一层中 (i, cw) 重复的状态（节点）合并，只记录 cv 值最大的那个状态
    public static int knapsack3(int[] weight, int[] value, int n, int w) {
        int[][] states = new int[n][w+1];
        for (int i = 0; i < n; ++i) { // 初始化states
            for (int j = 0; j < w+1; ++j) {
                states[i][j] = -1;
            }
        }
        states[0][0] = 0;
        if (weight[0] <= w) {
            states[0][weight[0]] = value[0];
        }
        for (int i = 1; i < n; ++i) { //动态规划，状态转移
            for (int j = 0; j <= w; ++j) { // 不选择第i个物品
                if (states[i-1][j] >= 0) states[i][j] = states[i-1][j];
            }
            for (int j = 0; j <= w-weight[i]; ++j) { // 选择第i个物品
                if (states[i-1][j] >= 0) {
                    int v = states[i-1][j] + value[i];
                    if (v > states[i][j+weight[i]]) {
                        states[i][j+weight[i]] = v;
                    }
                }
            }
        }
        // 找出最大值
        int maxvalue = -1;
        for (int j = 0; j <= w; ++j) {
            if (states[n-1][j] > maxvalue) maxvalue = states[n-1][j];
        }
        return maxvalue;
    }


    //杨辉三角
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        if(numRows <= 0){
            return result;
        }
        List<Integer> before = new ArrayList<>();
        before.add(1);
        result.add(before);
        for(int index = 2; index<= numRows; index++){
            List<Integer> thisRow = new ArrayList<>();
            for(int j = 0; j < index ; j ++){
                int leftBefore = j - 1;
                int leftRight = j;
                int thisNum = 0;
                if(leftBefore >= 0){
                    thisNum += before.get(leftBefore);
                }
                if(leftRight < before.size()){
                    thisNum += before.get(leftRight);
                }
                thisRow.add(thisNum);
            }
            result.add(thisRow);
            before = thisRow;
        }



        return result;
    }



    public static void main(String[] args){
        int maxCurrentWeight = 0;
        put(0,0);
        System.out.println(maxCurrentWeight);
    }





}
